#define _CRT_SECURE_NO_WARNINGS 1

#include "Heap.h"

//堆的初始化
void HPInit(HP* php)
{
	//不能传空指针
	assert(php);
	//指针初始化为空指针
	php->arr = NULL;
	//有效元素个数和空间大小初始化为0
	php->capacity = php->size = 0;
}
//堆的销毁
void HPDestroy(HP* php)
{
	//不能传空指针
	assert(php);
	if (php->arr != NULL)
		//释放动态申请的空间
		free(php->arr);
	//指向堆的指针置为空
	php->arr = NULL;
	//将空间大小和有效元素个数置为0
	php->capacity = php->size = 0;
}

//交换函数
void Swap(int* x, int* y)
{
	int z = *x;
	*x = *y;
	*y = z;
}

//向上调整算法
void AdjustUp(HPDataType* a, int child)
{
	//根据子节点计算父节点
	int parent = (child - 1) / 2;
	//当child为0的时候就应该停止调整。
	while (child > 0)
	{
		//判断子节点是否小于父节点,如果小于父节点,就交换，否则直接退出
		if (*(a + child) > *(a + parent))
		{
			//交换
			Swap(a + child, a + parent);
			//计算交换后的节点对应的父节点
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

//堆的插入
void HPPush(HP* php, HPDataType x)
{
	//不能传空指针
	assert(php);
	//判断空间是否足够
	if (php->capacity == php->size)
	{
		//计算增容的大小
		int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		//使用realloc增容
		HPDataType* newArr = (HPDataType*)realloc(php->arr,sizeof(HPDataType)*newCapacity);
		//判断realloc的返回值
		if (newArr == NULL)
		{
			//realloc的返回值如果为空就打印错误信息,并且退出程序
			perror("realloc error!\n");
			exit(1);
		}
		//将扩容后的地址赋给结构体成员
		php->arr = newArr;
		//将新的空间大小赋给结构体成员
		php->capacity = newCapacity;
	}
	//插入值
	*(php->arr + php->size) = x;
	//为了保证是有效的小堆,调用向上调整算法,使其变成小堆
	AdjustUp(php->arr, php->size);
	//有效元素个数自增
	++php->size;
}
//向下调整算法
//             要调整的数组,从哪个位置开始,堆的有效数据个数
void AdjustDown(HPDataType* a, int parent, int n)
{
	//计算左子树
	int child = 2 * parent + 1;//2i+1
	//child小于n就说明
	while (child < n)
	{
		//小堆: 找左右孩子中最小的
		//大堆: 找左右孩子中左大的
		//计算左右子树哪个小
		if (child+1 < n && *(a + child) > *(a + child + 1))
		{
			//如果右子树小就让child++，指向右子树
			child++;
		}
		//判断当前节点和子节点哪个小,若子节点小则需要交换,否则退出
		if (*(a + child) < *(a + parent))
		{
			//交换
			Swap(a + child, a + parent);
			//parent跟着调整的节点的位置走
			parent = child;
			//child继续计算出parent节点的左子树节点
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}
// 删除堆顶的数据
void HPPop(HP* php)
{
	//不能传空指针以及堆不能为空
	assert(php && php->size);
	//首先交换堆顶的数据和最后一个数据
	Swap(php->arr, php->arr + php->size - 1);
	//有效元素个数-1
	--php->size;
	//堆的向下调整算法
	AdjustDown(php->arr, 0, php->size);
}
//取堆顶数据
HPDataType HPTop(HP* php)
{
	//不能传空指针以及堆不能为空
	assert(php && php->size);
	//返回下标为0的数据
	return *php->arr;
}
// 判空
bool HPEmpty(HP* php)
{
	//不能传空指针
	assert(php);
	//有数据就返回true,否则返回false
	return php->size;
}
